The present invention relates generally to data routing systems and, more particularly, to routing packets through a network switch.
Ethernet is a widely-installed local area network technology. Specified in a standard, Institute of Electrical and Electronic Engineers (IEEE) 802.3, Ethernet was originally developed by Xerox and then developed further by Xerox, DEC, and Intel. An Ethernet LAN typically uses coaxial cable or special grades of twisted pair wires. A commonly installed Ethernet systems are called 10BASE-T and provide transmission speeds up to 10 Mbps. Devices are connected to the cable and compete for access using a Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol. Fast Ethernet or 100BASE-T provides transmission speeds up to 100 megabits per second and may be used for LAN backbone systems, supporting workstations with 10BASE-T cards. Gigabit Ethernet provides an even higher level of backbone support at 1000 megabits per second (1 gigabit or 1 billion bits per second).
Fast Ethernet is a local area network transmission standard that provides a data rate of 100 megabits per second (referred to as xe2x80x9c100BASE-Txe2x80x9d). Workstations with existing 10 megabit per second (10BASE-T) Ethernet card can be connected to a Fast Ethernet network. (The 100 megabits per second is a shared data rate; input to each workstation is constrained by the 10 Mbps card). Gigabit Ethernet is a local area network transmission standard that provides a data rate of 1 billion bits per second (one gigabit). Gigabit Ethernet is defined in the IEEE 802.3 standard. Gigabit Ethernet may be used as an enterprise backbone. Gigabit Ethernet may be carried on optical fibers (with very short distances possible on copper media). Existing Ethernet LANs with 10 and 100 Mbps cards can feed into a Gigabit Ethernet backbone.
Data may be sent over a packet switching network using digital signals. In a packet switching network, users can share the same paths at the same time and the route a data unit travels can be varied as conditions change. In packet-switching, a message is divided into packets, which are units of a certain number of bytes. The network addresses of the sender and of the destination are added to the packet. Each network point looks at the packet to see where to send it next. Packets in the same message may travel different routes and may not arrive in the same order that they were sent. At the destination, the packets in a message are collected and reassembled into the original message.
Layering is the organization of programming into separate steps that are performed sequentially, defined by specific interface for passing the result of each step to the next program or layer until the overall function, such as the sending or receiving of some amount of information, is completed. Communication programs are often layered. The reference model for communication programs, Open System Interconnection (OSI) is a layered set of protocols in which two programs, one at either end of a communications exchange, use an identical set of layers. OSI includes of seven layers, each reflecting a different function that has to be performed in order for program-to-program communication to take place between computers. Transmission Control Protocol and Internet Protocol (TCP/IP) is an example of a two-layer set of programs that provide transport and network address functions for Internet communication.
A switch is a internetworking device that selects a path or circuit for sending a unit of data to its next destination. A switch may also include the function of a router and determine the route and specifically what adjacent network point the data should be sent to. Relative to the layered Open Systems Interconnection (OSI) communication model, a switch may be associated with the data link layerxe2x80x94Layer 2. Switches may also be capable of performing the routing functions of the network layerxe2x80x94Layer 3. Layer 3 switches are also sometimes called IP switches.
The Data Link Layer of OSIxe2x80x94Layer 2xe2x80x94is concerned with moving data across the physical links in the network. In a network, a switch may be a device that redirects data messages at the Layer 2 level, using the destination Media Access Control (MAC) address to determine where to direct the message. The Data-Link Layer contains two sublayers that are described in the IEEE-802 LAN standards: Media Access Control (MAC), and Logical Link Control (LLC). The Data Link Layer assures that an initial connection has been set up, divides output data into data frames, and handles the acknowledgements from a receiver that the data arrived successfully. It also ensures that incoming data has been received successfully by analyzing bit patterns at special places in the frames.
The Network Layer of OSIxe2x80x94Layer 3xe2x80x94 is concerned with knowing the address of the neighboring nodes in the network, selecting routes and quality of service, and recognizing and forwarding to the transport layer incoming messages for local host domains. A switch may be a Layer 3 device and perform layer 3 functions. The IP address is a layer 3 address.
Switching, does by its nature, involves transient data flows. At Gigabit speeds, these transients occur extremely fast, and in a highly random manner. In the past, it has been difficult to determine in sufficiently fast enough speeds which components of a switch data flows should be directed to so as maximize data flow through the switch and reduce blocking traffic in the switch.
A system, method and article of manufacture are provided for updating a switching table in a switch fabric. In general, one or more status packets are received by a switch fabric component without handshaking between the transmitting source(s) and the receiving switch fabric component. Each status packet includes information relating to a status of an output port. A switching table is then updated based on the status information of the received status packet.
In an aspect of the present invention, the status packets may be received via paths/channels/conduits dedicated for transmitting the status packets and separate from paths dedicated for transmitting Ethernet packets through the switch fabric system. In another aspect of the present invention, the status packets may be received periodically and the switching table may be updated in real time.
In an embodiment of the present invention, a combined status packet may be generated based on the combined status information of the received status packets. The combined status packet may then be transmitted to other switch fabric components. In one aspect of such an embodiment, the combined status packet may be transmitted from an outer layer switch fabric component to a middle layer switch fabric component.
In one aspect of the present invention, the received status packet may be generated from a port controller. In a further aspect of the present invention, the received status packet may be generated by a switch fabric component. In yet another aspect of the present invention, the status packet may comprise 32 bits of data with each bit being associated with a port of the switch fabric component.
The foregoing and other features, aspects and advantages are better understood from the following detailed description, appended claims, and accompanying drawings where:
FIG. 1 is a schematic block diagram of a multi-port switch architecture in accordance with an embodiment of the present invention;
FIG. 2 is a schematic block diagram of another multi-port switch architecture in accordance with an embodiment of the present invention;
FIG. 3 is a schematic block diagram of a gigabit up-linking in accordance with an embodiment of the present invention;
FIG. 4 is a schematic block diagram of an architecture of a port controller in accordance with an embodiment of the present invention;
FIG. 5 is a flowchart of a process for preparing a datagram for transmission through a switch fabric in accordance with an embodiment of the present invention;
FIG. 6 is a schematic representation of an illustrative packet in accordance with an embodiment of the present invention;
FIG. 7 is a flowchart for a process for processing packets in accordance with an embodiment of the present invention;
FIG. 8 is a first schematic flow diagram illustrating the process for processing packets set forth in FIG. 7 in a port controller in accordance with an embodiment of the present invention;
FIG. 9 is a second schematic flow diagram illustrating the process for processing packets set forth in FIG. 7 in a port controller in accordance with an embodiment of the present invention;
FIG. 10 is a schematic diagram representing an illustration of the processing and storing of a plurality of incoming packets entering a port controller in accordance with an embodiment of the present invention;
FIG. 11 is a flowchart for a process for separating a header portion from a body portion of a packet in accordance with an embodiment of the present invention;
FIG. 12 is a flowchart for a process for storing a body portion of a packet in memory after separation from the header portion in accordance with an embodiment of the present invention;
FIG. 13 is a flowchart for a process for storing a processed header portion of a packet in memory in accordance with an embodiment of the present invention;
FIG. 14 is a schematic diagram representing the storing of cells of an incoming packet into memory in accordance with an embodiment of the present invention;
FIG. 15 is a flowchart of a process for transferring a packet from a port controller to a switch fabric in a switch fabric system in accordance with an embodiment of the present invention;
FIG. 16 is a flowchart of a process for generating linked lists of packets queued for egress in accordance with an embodiment of the present invention;
FIG. 17 is a schematic diagram depicting the linking of packets stored in the packet memory to their assigned output priority queues in accordance with an embodiment of the present invention;
FIG. 18 is a schematic diagram illustrating an exemplary packet stored in the packet memory illustrated in FIG. 17 in accordance with an embodiment of the present invention;
FIG. 19 is a schematic flow diagram illustrating a process for processing a packet exiting a switch system via a port controller in accordance with an embodiment of the present invention;
FIG. 20 is a schematic block diagram of an architecture of a switch fabric component in accordance with an embodiment of the present invention;
FIG. 21 is a flowchart of a process for sending a datagram through a switch fabric in accordance with an embodiment of the present invention;
FIG. 22 is a schematic block diagram of a switch fabric comprising four 8 by 8 switch fabric components to illustrate the implementation of switching tables for routing packets through the switch fabric in accordance with an embodiment of the present invention;
FIGS. 23, 24, 25, 26 are schematic illustrations of exemplary switching tables for the switch fabric depicted in FIG. 22 in accordance with an embodiment of the present invention;
FIG. 27 is a flowchart for a process for processing a packet through a switch fabric component in accordance with an embodiment of the present invention;
FIG. 28 is a schematic diagram illustrating a process for processing a packet through a switch fabric component where the determination result comprises a port bitmap in accordance with an embodiment of the present invention;
FIG. 29 is a schematic diagram illustrating an exemplary utilization of a port bitmap (in particular, an 8 bit port bitmap) in a switch fabric component in accordance with an embodiment of the present invention;
FIG. 30 is a schematic representation of an exemplary destination vector, an egress mask for the destination vector and a modified destination vector in accordance with an embodiment of the present invention;
FIG. 31 is a schematic diagram illustrating another process for processing a packet through a switch fabric component where the determination result comprises a destination vector in accordance with an embodiment of the present invention;
FIG. 32 is a flowchart of a process for updating a switching table in a switch fabric in accordance with an embodiment of the present invention;
FIG. 33 is a schematic diagram illustrating an exemplary arrangement for back propagation of status and control information in a switch fabric in accordance with an embodiment of the present invention;
FIG. 34 is a flowchart of a process for updating switching tables in a switch fabric system in accordance with an embodiment of the present invention;
FIG. 35 is a schematic representation of a status packet that may be utilized in the process set forth in FIG. 34 in accordance with a preferred embodiment of the present invention;
FIG. 36 is a flowchart of a process for storing an incoming datagram in a switch matrix of a switch fabric in accordance with an embodiment of the present invention;
FIG. 37 is a schematic diagram illustrating the ingress and storage of packets (i.e., datagrams) in a switch fabric component in accordance with an embodiment of the present invention;
FIG. 38 is a schematic diagram of a scenario illustrating the ingress and storage of packets in a switch fabric component having a pair of two-portion input buffers and a two-memory-bank switch matrix in accordance with an embodiment of the present invention;
FIG. 39 is a schematic diagram of the scenario set forth in FIG. 38 at cycle count 23 in accordance with an embodiment of the present invention;
FIG. 40 is a schematic diagram of the scenario set forth in FIG. 38 at cycle count 103 in accordance with an embodiment of the present invention;
FIG. 41 is a schematic illustration of a scenario similar to scenario presented in FIG. 38 where trivial dual input buffers are used instead of the dual two-portion buffers used in FIG. 38 in accordance with an embodiment of the present invention;
FIG. 42 is a schematic diagram illustrating memory access size for a switch matrix memory bank in accordance with an embodiment of the present invention; and
FIG. 43 is a schematic diagram of a hardware implementation of one embodiment of the present invention.